package com.tree.leetcode.array;

import cn.hutool.json.JSONUtil;

import java.util.Stack;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 42. 接雨水
 * <p>
示例 1：
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
    输入：height = [4,2,0,3,2,5]
    输出：9
 * </p>
 * @Author tree
 * @Date 3/16/24 11:35 AM
 * @Version 1.0
 */
public class Trap_42 {
    public static void main(String[] args) {
        int[] height = {4,2,0,3,2,5};
        System.out.println(trap2(height));


        int[] nums1={1,2,3,0,0,0};
        int[] nums2={2,4,5};
        int m = nums1.length;
        int n = nums2.length;

        int i = nums1.length;
        while(n>0){
            System.out.println("nums1= "+JSONUtil.toJsonStr(nums1)+",nums2="+JSONUtil.toJsonStr(nums2));
            if(m>0 && nums1[m-1]>nums2[n-1]){
//                i--;
//                m--;
                nums1[--i] = nums1[--m];
                //i--;
                //m--;
            }else{
                nums1[--i] = nums2[--n];
                //i--;
                //n--;
            }
        }

    }


    /**
     单调栈 */
    public static int trap2(int[] height) {

        int n = height.length;
        if(n <= 2) return 0;
        int sum = 0;
        // 单调栈， 存放数组索引, 单调递增
        Stack<Integer> stack = new Stack();
        stack.push(0);
        for(int i =1 ; i < n; i++){
            int top = stack.peek();
            int currentH = height[i];
            if(currentH < height[top]){
                stack.push(i);
            }else if (currentH == height[top]){
                //如果两个数字高度相等，那么可以把后面替换
                stack.pop();
                stack.push(i);
            }else{
                //当前元素循环比较单调栈的所有元素， 直至单调栈元素大于当前元素
                while(!stack.isEmpty() && currentH > height[top]){
                    //出栈
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int left = stack.peek();
                        int right = i;
                        int w = right-left -1;
                        int h = Math.min(height[left], height[right])- height[mid];
                        int cuurentSum = h*w;
                        sum+=cuurentSum;
                        // 更新top， 因为需要拿当前值与栈顶元素对比
                        top = stack.peek();
                    }
                }
                stack.push(i);
            }
        }
        return sum;

    }

    /**
     暴力解法
     */
    public static int trap1(int[] height) {
        int n = height.length;
        int sum =0;
        for(int i  =0 ;i< n;i++){
            // 第一个柱子和最后一个柱子不接雨水
            if(i ==0 || i == n-1) continue;
            //左边最大高度
            int leftMax = height[i];
            //从i往前找最大左边高度
            for(int j=i-1; j >= 0; j--){
                leftMax = Math.max(leftMax, height[j]);
            }
            //右边最大高度
            int rightMax = height[i];
            for(int j = i+1; j<n; j++){
                rightMax = Math.max(rightMax, height[j]);
            }

            int width = 1;
            int minHeight = Math.min(leftMax,rightMax);

            //每次只计算1个格子的宽度， 即width为1， 能纯水的最小高度为minHeight-  height[i]
            int current =(minHeight-  height[i])*width;
            sum += current;
        }

        return sum;

    }
}
